package madixin.t739;

import java.util.Stack;

class Solution {

    /**
     * 用栈记录之前的数
     */
    public int[] dailyTemperatures(int[] T) {

        Stack<Integer> stack = new Stack<Integer>();

        int[] next = new int[T.length];//数组默认为0
        for (int i = 0; i < T.length; i++) {
            while (!stack.isEmpty() && T[i] > T[stack.peek()]) {
                int pre = stack.pop();
                next[pre] = i - pre;
            }
            stack.push(i);
        }
        return next;
    }


    /**
     * n*n算法
     */
    public int[] dailyTemperatures1(int[] T) {

        int[] next = new int[T.length];
        for (int i = 0; i < T.length; i++) {
            next[i] = 0;
            for (int j = i + 1; j < T.length; j++) {
                if (T[j] > T[i]) {
                    next[i] = j - i;
                    break;
                }
            }
        }

        return next;
    }
}